package com.zll.study.排列组合;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LeetCode第77题组合 {

    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return result;
    }

    // 回溯方法
    public void backtracking(int n,int k,int startIndex){
        // path.size()==k：压入result中
        if(path.size()==k){
            result.add(new ArrayList<>(path));
            return;
        }
        // startIndex就是防止出现重复的组合
        for(int i = startIndex;i<=n;i++){
            path.add(i); // 处理节点
            backtracking(n,k,i+1);  // 递归
            path.removeLast();  // 回溯，撤销处理的节点
        }
    }
}
